#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/letter-case-permutation/

class Solution {
    vector<string> ret;
    string path;
public:
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }

    void dfs(string s, int start)
    {
        if (path.size() == s.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++)
        {
            path.push_back(s[i]);
            dfs(s, i + 1);
            path.pop_back();

            if (s[start] >= 'a' && s[start] <= 'z')
            {
                -
                    char a = s[start] - 32;
                path.push_back(a);
                dfs(s, i + 1);
                path.pop_back();
            }

            if (s[start] >= 'A' && s[start] <= 'Z')
            {
                char a = s[start] + 32;
                path.push_back(a);
                dfs(s, i + 1);
                path.pop_back();
            }
        }


    }
};